Expected Time to Hit Zero

Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!

Let $DU(0, n)$ be the discrete uniform distribution on $0$ , $1$ , ..., $n-1$ . Define random variables as below.

$X_1 \sim DU(0, n)$

$X_{i+1} \sim DU(0, X_{i}) \ for \ i \ge 1$

The above process is repeated until we get a random variable with the value zero. What is the expected number of variables (i.e., time to hit zero) in this process?

Let $T_n$ be the time needed to hit zero.

$\begin{align*} t_n &=E(T_n) = E\left(E(T_n|X_1)\right) \\ &= \sum_{i=0}^{n-1} \frac{1}{n} E(T_n|X_1=i) \\ &= \sum_{i=0}^{n-1} \frac{1}{n} (1 + E(T_i)) \\ &= \sum_{i=0}^{n-1} \frac{1}{n} (1 + t_i) \end{align*}$

$nt_n = n + \sum_{i=0}^{n-1} t_i$

$(n-1)t_{n-1} = (n-1) + \sum_{i=0}^{n-2} t_i$

$nt_n = n + t_{n-1} + (n-1)t_{n-1} - (n-1) = nt_{n-1} + 1$

$t_n - t_{n-1} = \frac{1}{n}$

$\sum_{i=1}^n (t_i - t_{i-1}) = \sum_{i=1}^n \frac{1}{i}$

$t_0 = 0$

$t_n = \sum_{i=1}^n \frac{1}{i}$

Ben Chuanlong Du's Blog

It is never too late to learn.

Expected Time to Hit Zero

Comments